#include <stdio.h>

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};


class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};


// quick_sort
void quick_sort(int q[], int l, int r) {
    if (l >= r) {
        return;
    }

    int i = l - 1;
    int j = r + 1;
    int mid = q[l + r >> 1];
    while (i < j) {
        do i++; while (q[i] < mid);
        do j--; while (q[j] > mid);
        if (i < j) {
            std::swip(q[i], q[j]);
        }

        quick_sort(q, l, j);
        quick_sort(q, j + 1, r);
    }
}



// i is the index of less then key
int partition(int* a, int left, int right) 
{
    int key = a[left];
    int i = left;
    int j = 0;
    for (j = left + 1; j <= right; ++j) {
        if (a[j] <= key) {
            i++;
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    a[left] = a[i];
    a[i] = key;
    return i;
}

// 在数组a中[left, right]求排在第k[1..len(arr)]的数
// 左半（包括q）有j = q - p + 1个元素。如果k < j，
// 只需要在左半找第k大元素；如果k > j，需要在右半找第k - j大元素
int select(int* a, int left, int right, int k)
{
    if (left == right) return left;
    int p = partition(a, left, right);
    int num = p - left + 1;
    if (k == num) {
        return p;
    } else if (k < num) {
        return select(a, left, p, k);
    } else {
        return select(a, p + 1, right, k - num);
    }
}

void print(int* a, int len)
{
    int i = 0;
    for (i = 0; i < len; i++) {
        fprintf(stdout, "%d ", a[i]);
    }
    fprintf(stdout, "\n");
}

int select2(int* x, int len, int k) {
    int l = 0, u = len - 1;
    while(l < u){
        int m = l;   
        int i;
        for(i = l + 1; i <= u; i++) {
            if(x[i] < x[l]) {
                ++m;
                int tmp = x[m];
                x[m] = x[i];
                x[i] = tmp;
            }
        }
        int tmp = x[l];
        x[l] = x[m];
        x[m] = tmp;
        if(k <= m) u = m - 1;
        if(k >= m) l = m + 1;
    }
    return x[k];
}

int main () {
    int arr[] = {4,3,2,9,1,6,5};
    int len = sizeof(arr) / sizeof(arr[0]);
    int k = 0;
    int tmp = select2(arr, len, k);
    fprintf(stdout, "第%d大数为%d\n", k, tmp);
    //int tmp = select(arr, 0, len - 1, k);
    //fprintf(stdout, "第%d大数为a[%d]\n", k, tmp);
    print(arr, len);
    return 0;
}
